Chinese Remainder Theorem

Introduction

The Chinese Remainder Theorem is a classical result in number theory that can be elegantly generalized to the language of ring theory. It provides a powerful tool for solving systems of congruences and understanding the structure of rings with multiple ideals.

Statement

Theorem 10.2 (Chinese Remainder Theorem for Rings): Let $R$ be a commutative ring and let $I_{1}, I_{2}, \dots, I_{k}$ be ideals of $R$ . If the ideals are pairwise coprime (or comaximal), meaning $I_{i} + I_{j} = R$ for all $i \neq j$ , then the natural ring homomorphism

ϕ : R \to (R / I_{1}) \times (R / I_{2}) \times \dots \times (R / I_{k})

defined by $ϕ (x) = (x + I_{1}, x + I_{2}, \dots, x + I_{k})$ is surjective. Furthermore, its kernel is the intersection of the ideals, $\ker (ϕ) = ⋂_{j = 1}^{k} I_{j}$ . By the First Isomorphism Theorem for rings, this induces an isomorphism:

R / (⋂_{j = 1}^{k} I_{j}) ≅ (R / I_{1}) \times (R / I_{2}) \times \dots \times (R / I_{k})

Since for pairwise coprime ideals, their intersection is equal to their product, we have $⋂ I_{j} = \prod I_{j}$ .

Classical Version

The classical Chinese Remainder Theorem states that if $n_{1}, n_{2}, \dots, n_{k}$ are pairwise coprime integers, then the system of congruences

x \equiv a_{1} (\mod n_{1})

x \equiv a_{2} (\mod n_{2})

⋮

x \equiv a_{k} (\mod n_{k})

has a unique solution modulo $n_{1} n_{2} \dots n_{k}$ .

Examples

Example 1: Integers

Consider the ideals $(3)$ , $(5)$ , and $(7)$ in $Z$ . These are pairwise coprime, so by the Chinese Remainder Theorem:

Z / (105) ≅ Z / (3) \times Z / (5) \times Z / (7)

Example 2: Polynomial Rings

Consider the ideals $(x - 1)$ and $(x + 1)$ in $R [x]$ . These are coprime, so:

R [x] / (x^{2} - 1) ≅ R [x] / (x - 1) \times R [x] / (x + 1) ≅ R \times R

Example 3: Solving Congruences

To solve the system:

x \equiv 2 (\mod 3)

x \equiv 3 (\mod 5)

x \equiv 2 (\mod 7)

We can use the Chinese Remainder Theorem to find a solution modulo $3 \times 5 \times 7 = 105$ .

Applications

Application 1: Number Theory

The Chinese Remainder Theorem is fundamental in number theory for solving systems of congruences.

Application 2: Cryptography

The Chinese Remainder Theorem is used in the RSA cryptosystem and other cryptographic protocols.

Application 3: Error-Correcting Codes

The theorem is used in the construction of error-correcting codes.

Application 4: Ring Structure

The theorem helps understand the structure of rings with multiple ideals.

Proof Sketch

The proof involves:

Showing that the map $ϕ$ is well-defined
Proving that $ϕ$ is a ring homomorphism
Establishing surjectivity using the coprimality condition
Identifying the kernel as the intersection of the ideals
Applying the First Isomorphism Theorem